1036D - Vasya and Arrays - CodeForces Solution


greedy two pointers *1600

Please click on ads to support us..

Python Code:

import gc
import heapq
import itertools
import math
import sqlite3
from collections import Counter, deque, defaultdict
from sys import stdout
import time
from math import factorial, log, gcd
import sys
from decimal import Decimal
import threading
from heapq import *


def S():
    return sys.stdin.readline().split()


def I():
    return [int(i) for i in sys.stdin.readline().split()]


def II():
    return int(sys.stdin.readline())


def IS():
    return sys.stdin.readline().replace('\n', '')


def main():
    n, a = II(), I()
    m, b = II(), I()
    s1, s2 = map(sum, [a, b])
    if s1 != s2:
        print(-1)
        return
    if a == b:
        print(n)
        return
    idx_a = 1
    idx_b = 0
    s_a = a[0]
    s_b = 0
    ans = 0
    while True:
        if s_a > s_b:
            s_b += b[idx_b]
            idx_b += 1
        elif s_a < s_b:
            s_a += a[idx_a]
            idx_a += 1
        else:
            ans += 1
            if idx_a == n:
                break
            idx_a += 1
            s_a = a[idx_a - 1]
            s_b = 0
    print(ans)


if __name__ == '__main__':
            main()

C++ Code:

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <complex>
#include <queue>
#include <set>
#include <unordered_set>
#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <fstream>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
ll MOD = 998244353;
double eps = 1e-12;
#define forn(i,e) for(ll i = 0; i < e; i++)
#define forsn(i,s,e) for(ll i = s; i < e; i++)
#define rforn(i,s) for(ll i = s; i >= 0; i--)
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF 2e18
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())



void solve(){
    ll n1;
    cin>>n1;

    ll a[n1];
	ll sum1=0;
    forn(i,n1){
        cin>>a[i];
		sum1+=a[i];
    }
	
	ll n2;
	cin>>n2;
	ll sum2=0;
    ll b[n2];
	forn(i,n2){
		cin>>b[i];
		sum2+=b[i];
	}
	
	if(sum1!=sum2){
		cout<<-1<<endl;
		return;
	}
	
	ll x=a[0],y=b[0];
	ll i=1,j=1;
	ll ans=0;
	while(i<n1 && j<n2){
		if(x<y){
			x+=a[i];
			i++;
		}
		else if(y<x){
			y+=b[j];
			j++;
		}
		else{
			ans++;
			x=a[i];
			y=b[j];
			i++;
			j++;
		}
	}
	
	ans++;
	
	cout<<ans<<endl;
}


int main()
{
    fast_cin();
    ll t=1;
    // cin >> t;
    for(int ix=1;ix<=t;ix++) {
        solve();
    }
    return 0;
}
   		 			 	 			 	  	 			 	  	 	


Comments

Submit
0 Comments
More Questions

1612A - Distance
520A - Pangram
124A - The number of positions
1041A - Heist
901A - Hashing Trees
1283A - Minutes Before the New Year
1654D - Potion Brewing Class
1107B - Digital root
25A - IQ test
785A - Anton and Polyhedrons
1542B - Plus and Multiply
306A - Candies
1651C - Fault-tolerant Network
870A - Search for Pretty Integers
1174A - Ehab Fails to Be Thanos
1169A - Circle Metro
780C - Andryusha and Colored Balloons
1153A - Serval and Bus
1487C - Minimum Ties
1136A - Nastya Is Reading a Book
1353B - Two Arrays And Swaps
1490E - Accidental Victory
1335A - Candies and Two Sisters
96B - Lucky Numbers (easy)
1151B - Dima and a Bad XOR
1435B - A New Technique
1633A - Div 7
268A - Games
1062B - Math
1294C - Product of Three Numbers